package eda.skipList;

import java.util.NoSuchElementException;
import eda.util.ADTOverflowException;
import eda.util.ADTUnderflowException;

/**
 * Estrutura representa uma skip list. Ela tem uma probabilidade e pode ou nao
 * usar o nivel maximo como nivel da lista logo na criacao. Isso eh informado
 * pelo usuario na criacao. A estrutura guarda apenas a raiz da lista. A
 * estrutura deve ter um tamanho inicial, um tamanho maximo que pode crescer e
 * um FATOR de crescimento. Quando instanciada a estrutura tem um tamanho
 * inicial. Quando ela vai crescendo e enche, ela aumenta de tamanho de acordo
 * com o fator de crescimento desde que nao atinja ou ultrapasse o tamanho
 * maximo. A partir dai a estrutura nao pode mais crescer e pode ficar cheia.
 * Use as constantes definidas em eda.util.Constantes para inicializar os
 * valores internos de sua estrutura. Faca protected qualquer outro metodo
 * auxiliar.
 */
public class SkipListImpl<V> implements SkipList<V> {

	protected static int level;
	protected SkipNode<V> raiz;
	protected SkipNode<V> NIL;
	protected int maxLevel;
	protected double probabilidade = 0.5;

	/**
	 * Construtor de uma Skip List
	 * 
	 * @param maxLevel
	 * 			a altura maxima de um no que pode ser inserido
	 * @param useMaxLevelAsInitialLevel
	 * 			parametro que define se o nivel maximo sera utilizado como
	 * 			nivel da Skip List
	 */
	public SkipListImpl(int maxLevel, boolean useMaxLevelAsInitialLevel) {
		this.maxLevel = maxLevel;

		if (useMaxLevelAsInitialLevel) {
			level = maxLevel;

		} else {
			level = 1;
		}

		raiz = new SkipNode(Integer.MIN_VALUE, maxLevel, "ROOT");
		NIL = new SkipNode(Integer.MAX_VALUE, maxLevel, "NIL");
		connectRootToNil();
	}

	/**
	 * Metodo que conecta todos os forwards da raiz ao NIL
	 */
	protected void connectRootToNil() {
		for (int i = 0; i < maxLevel; i++) {
			this.raiz.forward[i] = NIL;
		}
	}

	/**
	 * Metodo que gera um nivel randomico de um no a ser inserido na Skip List
	 * 
	 * @return
	 * 			o nivel gerado randomicamente
	 */

	protected int randomLevel() {
		int randomLevel = 1;
		while (Math.random() <= probabilidade && randomLevel < maxLevel) {
			randomLevel = randomLevel + 1;
		}
		return randomLevel;
	}

	/**
	 * metodo que insere um no na Skip List de uma altura gerada aleatoriamente
	 * 
	 * @param key
	 * 			chave a ser inserida
	 * @param newValue
	 * 			valor(dado) do objeto a ser inserido
	 * @throws ADTOverflowException
	 * 			se a capacidade da Skip List for excedida.
	 * @throws ADTUnderflowException
	 * 			se a chave a ser inserida for negativa
	 */

	//Adicionamos a excessao de undeflow para o caso de a chave ser negativa
	@Override
	public void insert(int key, V newValue) throws ADTOverflowException, ADTUnderflowException {
		SkipNode[] update = new SkipNode[this.maxLevel];
		SkipNode temp = this.raiz;
		int random = this.randomLevel();

		if(key < 0){
			throw new ADTUnderflowException();
		}

		if (this.size() == 90 || random > this.maxLevel) {
			throw new ADTOverflowException();
		}

		for (int i = level - 1; i >= 0; i--) {
			while (temp.forward[i].key < key) {
				temp = temp.forward[i];
			}
			update[i] = temp;
		}
		temp = temp.forward[0];
		if (temp.key == key) {
			temp.satteliteData = newValue;
		} else {
			if (random > this.level) {

				for (int i = random - 1; i >= this.level; i--) {
					update[i] = this.raiz;
				}
				this.level = random;

			}
			SkipNode noInsert = new SkipNode(key, random, newValue);
			for (int i = 0; i < random; i++) {
				noInsert.forward[i] = update[i].forward[i];
				update[i].forward[i] = noInsert;
			}
		}
	}

	/**
	 * metodo que insere um no na Skip List com uma altura especificada pelo
	 * usuario
	 * 
	 * @param key
	 *            chave a ser inserida
	 * @param newValue
	 *            valor(dado) do objeto a ser inserido
	 * @param height
	 *            altura do no a ser inserido
	 * @throws ADTOverflowException
	 *             se a capacidade da Skip List for excedida ou a altura do no a
	 *             ser inserido for superior ao nivel maximo da lista
	 * @throws ADTUnderflowException 
	 * 			   se a chave a ser inserida for negativa
	 */
	
	//Adicionamos a excessao de undeflow para o caso de a chave ser negativa
	@Override
	public void insert(int key, V newValue, int height)throws ADTOverflowException, ADTUnderflowException {

		if(key < 0 || height <= 0){
			throw new ADTUnderflowException();
		}

		if (this.size() == 90 || height > this.maxLevel) {
			throw new ADTOverflowException();
		}

		SkipNode[] update = new SkipNode[this.maxLevel];
		SkipNode temp = this.raiz;

		for (int i = level - 1; i >= 0; i--) {
			while (temp.forward[i].key < key) {
				temp = temp.forward[i];
			}
			update[i] = temp;
		}

		temp = temp.forward[0];

		if (temp.key == key) {
			temp.satteliteData = newValue;
		} else {
			if (height > level) {

				for (int i = height - 1; i >= this.level; i--) {
					update[i] = this.raiz;
				}
				level = height;

			}
			SkipNode noInsert = new SkipNode(key, height, newValue);
			for (int i = 0; i < height; i++) {
				noInsert.forward[i] = update[i].forward[i];
				update[i].forward[i] = noInsert;
			}
		}
	}

	/**
	 * metodo que remove um no da Skip List a partir de uma chave dada
	 * 
	 * @param key
	 *            chave do no a ser removido
	 * @throws ADTUnderflowException
	 *             se a chave dada for menor que 0
	 * @throws NoSuchElementException
	 *             se o no a ser removido nao for encontrado
	 */

	@Override
	public void remove(int key) throws ADTUnderflowException,
	NoSuchElementException {
		if (key < 0) {
			throw new ADTUnderflowException();
		}

		SkipNode[] update = new SkipNode[maxLevel];
		SkipNode temp = this.raiz;

		for (int i = level - 1; i >= 0; i--) {
			while (temp.forward[i] != null && temp.forward[i].key < key) {
				temp = temp.forward[i];
			}
			update[i] = temp;
		}

		temp = temp.forward[0];

		if (temp.key == key) {
			for (int i = 0; i < level; i++) {
				if (update[i].forward[i] != temp) {
					break;
				}
				update[i].forward[i] = temp.forward[i];
			}
			this.level = getHeight();
		} 
		else {
			throw new NoSuchElementException();
		}
	}

	/**
	 * metodo que retorna a altura da Skip List
	 * 
	 * @return
	 * 			a altura da Skip List
	 */

	@Override
	public int getHeight() {
		if (!isEmpty()) {
			for (int i = level - 1; i >= 0; i--) {
				if (this.raiz.forward[i].key != Integer.MAX_VALUE) {
					return this.raiz.forward[i].height;
				}
			}
		}
		return 0;
	}

	/**
	 * metodo que pesquisa um no com determinada chave da Skip List
	 * 
	 * @param key
	 * 			a chave do no a ser pesquisado
	 * @return
	 * 			o no pesquisado, caso encontrado
	 * @throws NoSuchElementException
	 * 			caso o no nao seja encontrado
	 */

	@Override
	public SkipNode<V> search(int key) {
		SkipNode<V> temp = this.raiz;

		for (int i = level - 1; i >= 0; i--) {
			while (temp.forward[i].key < key) {
				temp = temp.forward[i];
			}
			if (temp.forward[i].key == key) {
				return temp.forward[i];
			}
		}
		throw new NoSuchElementException();
	}

	/**
	 * metodo que retorna uma String com chave e altura de cada no da Skip List
	 * e as respectivas chaves as quais estah conectado
	 * 
	 * @return
	 * 			a String com os dados dos nos da Skip List
	 */

	@Override
	public String printSkipList() {
		SkipNode<V> no = this.raiz;
		StringBuilder sb = new StringBuilder();
		while (no.forward[0] != null) {
			sb.append(no.toString() + " ");
			no = no.forward[0];
		}
		return sb.toString().trim();
	}

	/**
	 * metodo que verifica se a Skip List estah vazia ou nao
	 * 
	 * @return
	 * 			true se a Skip List estah vazia e false caso contrario
	 */

	public boolean isEmpty() {
		return raiz.forward[0].key == Integer.MAX_VALUE;
	}

	/**
	 * Metodo que retorna o numero de nos(elementos) contidos na Skip List entre a raiz e o NIL
	 * 
	 * @return
	 * 			numero de nos(elementos)
	 */

	public int size() {
		SkipNode temp = this.raiz;
		int size = 0;
		while (temp.forward[0].key != Integer.MAX_VALUE) {
			temp = temp.forward[0];
			size++;
		}
		return size;
	}
}